#include<exception>
#include<cstddef>
#include<stdexcept>

#include"tree.h"

template <typename T>
class Heap {
	
	Tree<T> * tree;
	size_t num;
	unsigned depth;
	
	static void floatDown(Tree<T> & t) {
		if (t . getRight() == 0) {
			if (t . getLeft() == 0) {
				return;
			} else {
				if (t . getLeft() -> getNode() < t . getNode()) {
					swap(t, * t . getLeft());
					floatDown(* t . getLeft());
					return;
				} else {
					return;
				}
			}
		} else {
			if (t . getNode() < t . getLeft() -> getNode()) {
				if (t . getNode() < t . getRight() -> getNode()) {
					return;
				} else {
					swap(t, * t . getRight());
					floatDown(* t . getRight());
					return;
				}
			} else {
				if (t . getNode() < t . getRight() -> getNode()) {
					swap(t, * t . getLeft());
					floatDown(* t . getLeft());
					return;
				} else {
					if (t . getLeft() -> getNode() < t . getRight() -> getNode()) {
						swap(t, * t . getLeft());
						floatDown(* t . getLeft());
						return;
					} else {
						swap(t, * t . getRight());
						floatDown(* t . getRight());
						return;
					}
				}
			}
		}
	}			
	
	static void floatUp(Tree<T> & t) {
		if ((t . getParent() != 0) && (t . getNode() < t . getParent() -> getNode())) {
			swap(t, * t . getParent());
			floatUp(* t . getParent());
		}
	}
	
	Tree<T> * operator[] (size_t n) {
		if ((n > num) || (n == 0)) {
			throw std::out_of_range("Wrong heap address");
		} else {
			Tree<T> * res = tree;
			unsigned d = 1;
			while (n >> d != 0) ++d;
			--d;
			while (d != 0) {
				--d;
				if ((n >> d) % 2 == 0)
					res = res -> getLeft();
				else
					res = res -> getRight();
			}
			return res;
		}
	}				
	
	Tree<T> const * operator[] (size_t n) const {
		if ((n > num) || (n == 0)) {
			throw std::out_of_range("Wrong heap address");
		} else {
			Tree<T> const * res = tree;
			unsigned d = 1;
			while (n >> d != 0) ++d;
			--d;
			while (d != 0) {
				--d;
				if ((n >> d) % 2 == 0)
					res = res -> getLeft();
				else
					res = res -> getRight();
			}
			return res;
		}
	}				

	
	public:
	Heap() : tree(0), num(0), depth(0) {}
	Heap(T const & t) : tree(new Tree<T>(t)), num(1), depth(1) {}
	Heap(Heap const & h) : tree (new Tree<T>(*h.tree)), num(h . num), depth(h . depth) {}
	~Heap() { if (tree != 0) delete tree; }
	
	Heap & operator=(Heap const & h) {
		Tree<T> * savetree = tree;
		size_t savenum = num;
		unsigned savedepth = depth;
		try {
			if (h . tree != 0)
				tree = new Tree<T>(* h . tree);
			else
				tree = 0;
			num = h . num;
			depth = h . depth;
		} catch (...) {
			tree = savetree;
			num = savenum;
			depth = savedepth;
			throw std::bad_alloc();
		}
		delete savetree;
		return *this;
	}
	
	void insert(T const & t) {
		Tree<T> * newNode = 0;
		newNode = new Tree<T>(t);
		try {
			if (tree == 0) {
				tree = newNode;
				num = depth = 1;
			}
			else {
				++num;
				Tree<T> * insertat = operator[](num >> 1);
				if (num % 2 == 0)
					insertat -> appendLeft(newNode);
				else
					insertat -> appendRight(newNode);
				if (num == (1 << depth))
					++depth;
			}
			floatUp(*newNode);
		} catch(std::exception & e) {
			delete newNode;
			throw e;
		}
	}
	
	T const & peekMin() const {
		if (tree != 0)
			return tree -> getNode();
		else
			throw std::out_of_range("Heap is empty");
	}
	
	size_t size() const {
		return num;
	}
	
	T extractMin() {
		if (tree == 0)
			throw std::out_of_range("Heap is empty");
		T res = tree -> getNode();
		Tree<T> * last = operator[](num);
		int w = last -> whichChild();
		switch (w) {
			case 0:
				delete last;
				tree = 0;
				num = depth = 0;
				break;
			case 1:
				swap(* tree, * last);
				last -> getParent() -> trimRight();
				if (num == (1 << depth))
					--depth;
				--num;
				floatDown(* tree);
				break;
			case -1:
				swap(* tree, * last);
				last -> getParent() -> trimLeft();
				if (num == (1 << depth))
					--depth;
				--num;
				floatDown(* tree);
				break;
		}				
		return res;
	}
	
};

/*template <typename T>
class HeapIterator {
	Heap<T> * self;
	Tree<T> * elem;
	
	HeapIterator() : self(0), elem(0) {}
	HeapIterator(Heap<T> * s, Tree<T> * t) : self(s), elem(t) {}
		
	T & operator*() {
		return elem -> node;
	}
	
	T const & operator*() const {
		return elem -> node;
	}
	
	HeapIterator operator++() {
		
};*/
